public class 搜索插入位置 {

    public static void main(String[] args) {
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 3));
    }

    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            // 第一种公式：mid = left + (right - left) / 2
            //
            // 优点：避免left + right可能导致的整数溢出问题，适合编程实现。
            //
            // 例如：left = 2, right = 10，则mid = 2 + (10 - 2) / 2 = 6。
            //
            // mid = ((right - left) >> 1) + left; 也是第一种公式 右移一位就相当于除以2
            // 位运算通常比算术运算更快。然而，在现代处理器和编译器优化下，这种性能差异可能变得微不足道
            //
            // 第二种公式：mid = (left + right) / 2
            //
            // 缺点：当left和right都很大时，left + right可能超出整数范围，导致溢出。
            //
            // 例如：left = 2, right = 10，则mid = (2 + 10) /2 = 6


            int mid = (right + left) / 2 + left;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] == target) {
                return left;
            }
            if (nums[right] == target) {
                return right;
            }
            if (right - left <= 1) {
                if (target > nums[right]) {
                    return right + 1;
                }
                if (target > nums[left]) {
                    return right;
                }
                if (target < nums[left]) {
                    return left;
                }
                return mid;
            }
            if (nums[mid] < target) {
                left = mid;
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        return 0;
    }
}
